package com.foxzzz.greedy;

public class Solution135 {

    public int count(int n) {
        return (n * (n + 1)) / 2;
    }

    public int candy1(int[] ratings) {
        if (ratings.length <= 1) {
            return ratings.length;
        }
        int candies = 0;
        int up = 0;
        int down = 0;
        int old_slope = 0;
        for (int i = 1; i < ratings.length; i++) {
            int new_slope = (ratings[i] > ratings[i - 1]) ? 1 : (ratings[i] < ratings[i - 1] ? -1 : 0);
            if ((old_slope > 0 && new_slope == 0) || (old_slope < 0 && new_slope >= 0)) {
                candies += count(up) + count(down) + Math.max(up, down);
                up = 0;
                down = 0;
            }
            if (new_slope > 0)
                up++;
            if (new_slope < 0)
                down++;
            if (new_slope == 0)
                candies++;

            old_slope = new_slope;
        }
        candies += count(up) + count(down) + Math.max(up, down) + 1;
        return candies;
    }

    public int candy(int[] ratings) {
        if (ratings.length == 1) {
            return 1;
        }
        int leftCandy[] = new int[ratings.length];
        int rightCandy[] = new int[ratings.length];
        for (int i = 0; i < ratings.length; i++) {
            if (i == 0 || ratings[i] <= ratings[i - 1]) {
                leftCandy[i] = 1;
            } else {
                leftCandy[i] = leftCandy[i - 1] + 1;
            }
        }
        for (int i = ratings.length - 1; i >= 0; i--) {
            if (i == ratings.length - 1 || ratings[i] <= ratings[i + 1]) {
                rightCandy[i] = 1;
            } else {
                rightCandy[i] = rightCandy[i + 1] + 1;
            }
        }
        int sum = 0;
        for (int i = 0; i < ratings.length; i++) {
            sum += Math.max(leftCandy[i], rightCandy[i]);
        }
        return sum;
    }


    public static void main(String[] args) {
        System.out.println(new Solution135().candy(new int[]{1, 2, 87, 87, 87, 2, 1}));
        System.out.println(new Solution135().candy(new int[]{1, 0, 2}));
        System.out.println(new Solution135().candy(new int[]{1, 2, 2}));
    }
}
